372B - Counting Rectangles is Fun - CodeForces Solution

#include <bits/stdc++.h>

#define dbg(x) cerr << #x << " = " << (x) << "\n"
#define bit(n,k) (((n)>>(k))&1)
#define rep(i,a,b) for(long long i = (a); i <= (b); ++i)
#define per(i,a,b) for(long long i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int, int> i2;
typedef pair<ll, ll> ll2;
typedef long double ld;

const int N = 49;
int rect[N][N][N][N];
int dp[N][N][N][N];

void testcase() {
	
	int n, m, q; cin >> n >> m >> q;
	rep(i, 1, n) {
		rep(j, 1, m) {
			char c; cin >> c;
			if(c == '1') rect[i][j][i][j] = 1;
		}
	}
	rep(h, 1, n) {
		rep(w, 1, m) {
			rep(i, 1, n-h+1) {
				rep(j, 1, m-w+1) {
					rect[i][j][i+h-1][j+w-1] = rect[i][j][i+h-1][j+w-2]+rect[i][j][i+h-2][j+w-1]-rect[i][j][i+h-2][j+w-2]+rect[i+h-1][j+w-1][i+h-1][j+w-1];
				}
			}
		}
	}
	rep(h, 1, n) {
		rep(w, 1, m) {
			rep(i, 1, n-h+1) {
				rep(j, 1, m-w+1) {
					dp[i][j][i+h-1][j+w-1] = (rect[i][j][i+h-1][j+w-1] == 0 ? 1 : 0);
					
					dp[i][j][i+h-1][j+w-1] += dp[i][j][i+h-1][j+w-2];
					dp[i][j][i+h-1][j+w-1] += dp[i][j+1][i+h-1][j+w-1];
					dp[i][j][i+h-1][j+w-1] += dp[i+1][j][i+h-1][j+w-1];
					dp[i][j][i+h-1][j+w-1] += dp[i][j][i+h-2][j+w-1];
					
					dp[i][j][i+h-1][j+w-1] -= dp[i][j][i+h-2][j+w-2];
					dp[i][j][i+h-1][j+w-1] -= dp[i][j+1][i+h-2][j+w-1];
					dp[i][j][i+h-1][j+w-1] -= dp[i+1][j+1][i+h-1][j+w-1];
					dp[i][j][i+h-1][j+w-1] -= dp[i+1][j][i+h-1][j+w-2];
					dp[i][j][i+h-1][j+w-1] -= dp[i][j+1][i+h-1][j+w-2];
					dp[i][j][i+h-1][j+w-1] -= dp[i+1][j][i+h-2][j+w-1];
					
					dp[i][j][i+h-1][j+w-1] += dp[i+1][j][i+h-2][j+w-2];
					dp[i][j][i+h-1][j+w-1] += dp[i][j+1][i+h-2][j+w-2];
					dp[i][j][i+h-1][j+w-1] += dp[i+1][j+1][i+h-2][j+w-1];
					dp[i][j][i+h-1][j+w-1] += dp[i+1][j+1][i+h-1][j+w-2];
					
					dp[i][j][i+h-1][j+w-1] -= dp[i+1][j+1][i+h-2][j+w-2];
				}
			}
		}
	}
	while(q--) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		cout << dp[a][b][c][d] << "\n";
	}
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	//cin >> t;
	while(t--) testcase();

	return 0;
}